package com.company.ljh.easy;
//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//
//
//
// 示例 1：
//..
//
//输入：head = [1,2,2,1]
//输出：true
//
//
// 示例 2：
//
//
//输入：head = [1,2]
//输出：false
//
//
//
//
// 提示：
//
//
// 链表中节点数目在范围[1, 105] 内
// 0 <= Node.val <= 9
//
//
//
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
// Related Topics 栈 递归 链表 双指针
// 👍 1316 👎 0
import com.company.ljh.utils.ListNode;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.easy
 * @author:ljh
 * @createTime:2022/3/25 11:50
 * @version:1.0
 */
public class 回文链表 {
    /**
     * 1.快慢指针+翻转链表
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null||head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        //找到中间结点
        while (fast != null) {
            slow = slow.next;
            if (fast.next == null) {
                fast = null;
            } else {
                fast = fast.next.next;
            }
        }
        //翻转后半部分链表
        ListNode lastNode = null;
        ListNode thisNode = slow;
        ListNode nextNode = slow.next;
        while (thisNode != null) {
            thisNode.next = lastNode;
            lastNode = thisNode;
            thisNode = nextNode;
            if (nextNode != null) {
                nextNode = nextNode.next;
            }
        }
        fast = head;
        while (fast != null && lastNode != null) {
            if (fast.val != lastNode.val) {
                return false;
            }
            fast = fast.next;
            lastNode = lastNode.next;
        }
        return true;

    }
}
